# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 17_find_neatest_number.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/1/28 11:03
------------------------------------------
    给出一个正整数，找出这个正整数所有数字全排列的下一个数
    也就是，在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数

    demo:
        12345 -> 12354
        12354 -> 12435
        12435 -> 12453

    思路：
        1）从后向前查看逆序区域，找到逆序区域的前一位，也就是正序区的最后一位
        2）让逆序区的前一位和逆序区中大于它的最小的数字交换位置
        3）把原来的逆序区转为顺序状态（在更换完之后）
"""


def find_nestest_number(numbers: list):
    # 1.从后向前查看逆序区域，找到逆序区从左向右的第一位也就是正序区的最后一位，
    # 也就是正序区和逆序区的重叠或者说是交界的位的索引
    index = find_transfer_point(numbers)

    # 如果数字置换边界是0，说明整个数组已经逆序，无法得到更大的相同数字
    if index == 0:
        return None

    # 2.把逆序区域的前一位和逆序区域中刚刚大于它(也就是大于它的最小)的数字交换位置
    # 复制入参，避免直接修改入参
    # 这种复制，对象如果不是嵌套对象的话，一个改变不会影响另一个
    numbers_copy = numbers.copy()
    exchange_head(index, numbers_copy)

    # 3.把原来的逆序区转为顺序区
    reverse(index, numbers_copy)

    return numbers_copy


def find_transfer_point(numbers):
    for i in range(len(numbers) - 1, 0, -1):
        # 这里如果是逆序就不管（continue），但是遇到逆序变正序的边界开始起作用了
        # 此时的 i是正序区从左向右最后一位同时也是逆序区从左向右的第一位的索引，因为这两个区重叠或者交界部分的数字是同一个
        # 逆序突然变正序
        if numbers[i] > numbers[i - 1]:
            return i

    return 0


def exchange_head(index, numbers: list):
    """
        把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置
        :params index: 正序区从左向右最后一位的索引
    """
    head = numbers[index - 1]
    for i in range(len(numbers) - 1, 0, -1):
        if head < numbers[i]:
            numbers[index - 1] = numbers[i]
            numbers[i] = head
            break

    return numbers


def reverse(index, numbers):
    """
        把原来的逆序区转为顺序状态，这里是首位对称地换
        :params index: 逆序区第一个数的索引
    """
    i = index
    j = len(numbers) - 1

    while i < j:
        temp = numbers[i]
        numbers[i] = numbers[j]
        numbers[j] = temp
        i += 1
        j -= 1

    return numbers


def output_numbers(numbers):
    """
        output:
        12354
        12435
        12453
        12534
        12543
        13245
        13254
        13425
        13452
        13524
    """
    for i in numbers:
        print(i, end='')
    print()


def demo():
    my_numbers = [1, 2, 3, 4, 5]

    # 打印 12345之后的10个全排列
    for i in range(1, 199):
        my_numbers = find_nestest_number(my_numbers)
        print(f"No.{i}: ", end='')
        output_numbers(my_numbers)


if __name__ == '__main__':
    demo()
